// 指定长度，随机生成链表存储的二叉树

function biNode(value,left,right) {
    this.value = value || null;
    this.left = left || null;
    this.right = right || null;
} 

/**
 * 
 * @param {*} value 
 * @param {*} left 
 * @param {*} right 
 * @param {*} ltag 
 * @param {*} rtag
 * @description 线索二叉树的节点 
 */
function threadBiNode(value, left, right, ltag, rtag) {
    this.value = value || null;
    this.left = left || null;
    this.right = right || null;
    this.ltag = ltag || null;
    this.rtag = rtag || null;
}


/**
 * 
 * @param {int} num 节点数 
 * @description 随机生成一个给定节点的二叉树
 */
function createBiTree(num) {

    if(num === 0) {

        return null;
    }
    const root = new biNode(num); 
    
    const leftNum = Math.floor(Math.random()*100) % num;
    const rightNum = num - leftNum - 1;

    root.left = createBiTree(leftNum);
    root.right = createBiTree(rightNum);

    return root;
    
}

/**
 * 
 * @param {number} num 节点个数 n = num  sum = 2 * num + 1  
 * @description 层次遍历生成 sum 个节点的二叉树
 */
function createBitreeByLevelOrder(num) {

    const root = new biNode(0);
    let nodeArr = [];
    nodeArr.push(root);
    for(let i = 0;i < num;i++) {

        let temp = nodeArr.shift();
        temp.left = new biNode(temp.value * 2);
        temp.right = new biNode(temp.value * 2 + 1);
        nodeArr.push(temp.left);
        nodeArr.push(temp.right);
    }

    return root;
}


/**
 * 
 * @param {int} num 节点数 
 * @description 随机生成一个给定节点的未线索化的线索二叉树
 */
 function createBiTreeForThread(num) {

    if(num === 0) {

        return null;
    }
    const root = new threadBiNode(num);  
    console.log(num);
    const leftNum = Math.floor(Math.random()*100) % num;
    const rightNum = num - leftNum - 1;
    
    if(leftNum !== 0) {
        root.ltag = 0;
    }
    if(rightNum !== 0) {
        root.rtag = 0
    }
    root.left = createBiTreeForThread(leftNum);
    root.right = createBiTreeForThread(rightNum);

    return root;
    
}



/**
 * 
 * @param { biTree } tree 
 * @description 通过中序遍历线索化二叉树
 * 基本算法：对一棵二叉树中序遍历，再遍历的过程中，如果左右指针为空，则将它们改为前驱节点或后继节点的线索
 */
function createInThreadTree(tree) {
    let pre = null
    if(tree) {
        InThreadTree(tree, pre);
        console.log(pre,'pre-=-=-');
        
    }
}

function InThreadTree(tree, pre) {
    
    if(tree) {
        
        InThreadTree(tree.left, pre);
        console.log('in inThreadThree', tree.value)
        if(tree.left === null) {
            tree.left = pre;
            tree.ltag = 1;
        }
        // console.log('pre:' )
        if(pre && pre.right === null) {
            pre.right = tree;
            pre.rtag = 1;
        }
        pre = tree;
        InThreadTree(tree.right, pre);

    }
}


const tree = createBiTreeForThread(10);
console.log('--------------------------')
console.log(tree);
console.log('--------------------------')

createInThreadTree(tree)




module.exports = {

    createBiTree,
    createBitreeByLevelOrder
}


